#include <iostream>
#include <vector>
using namespace std;
class Solution
{
private:
    static const int N = 1010;
    int parent[N];
    int n;
    int find(int index)
    {
        return parent[index] == index ? parent[index] : parent[index] = find(parent[index]);
    }
    bool isSame(int u, int v) {
        return find(u) == find(v);
    }
    void join(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return ;
        parent[u] = v;
    }
    void init() {
        for(int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
    }
    bool isTree(vector<vector<int>> &edges, int deletedEdge) {
        init();
        for(int i = 0; i < n; ++i) {
            if(i == deletedEdge) continue;
            if(isSame(edges[i][0], edges[i][1])) {
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }
public : 
    vector<int> findRedundantDirectedConnection(vector<vector<int>> &edges)
    {
        int inDegree[N] = {0};
        vector<int> res;
        n = edges.size();
        for (int i = 0; i < n; ++i)
        {
            inDegree[edges[i][1]]++;
        }
        for (int i = n - 1; i >= 0; --i)
        {
            if (inDegree[edges[i][1]] == 2)
                res.push_back(i); // 记录边
        }
        if(res.size() > 0) {
            if(isTree(edges, res[0])) {
                return edges[res[0]];
            }else {
                return edges[res[1]];
            }
        }else {
            init();
            for(int i = 0; i < n; ++i) {
                if(isSame(edges[i][0], edges[i][1])) {
                    return edges[i];
                }else {
                    join(edges[i][0], edges[i][1]);
                }
            }
            return {};
        }
    }
};
